package cn.segment.core.dictionary;

import java.io.IOException;
import java.util.ArrayList;

import org.apache.commons.io.IOUtils;
import org.apache.commons.io.LineIterator;

/**
 * tree node collection include tree node root
 * 
 * @author Huang Yue
 * @version 创建时间：2010-6-7 下午06:42:41
 */
public class TreeBuild
{
    private TreeBuild() {
    };

    private int bug_index = 0;
    private TreeNode root = new TreeNode();
    private int count;

    /**
     * 创建新的结点集合
     * 
     * @return
     * @throws IOException 
     */
    public static TreeBuild create(String path, String encode) throws IOException
    {
        TreeBuild build = new TreeBuild();
        LineIterator lines = IOUtils.lineIterator(TreeBuild.class
                .getResourceAsStream(path), encode);
        while (lines.hasNext())
        {
            String word = lines.nextLine();
            build.addWord(word);
        }
        return build;
    }

    /**
     * 往树中添加一个词
     * 
     * @param word
     */
    public void addWord(String word)
    {
        if(word.equals("网络")){
            System.out.println();
        }
        if(contains(word)){
            return;
        }
        addNode(word, 0);
        count++;
    }

    private void addNode(String word, int index)
    {
        nodeInsertToTree(root, word, index);
    }

    /**
     * 插入树的方式为深度优先，首先向下延伸，在child node 已有数据的时候向两边延伸 node char 大于 child char 向右走，
     * 小于向左走
     * 
     * @param parent
     * @param node
     * @return
     */
    private void nodeInsertToTree(TreeNode current, String word, int index)
    {
        if (index == word.length())
        {
            return;
        }

        TreeNode child = current.child;
        char nodeChar = word.charAt(index++);
        // 当前节点子节点为空时优先填充子节点
        if (child == null)
        {
            current.child = new TreeNode(nodeChar, index == word.length());
            nodeInsertToTree(current.child, word, index);
            return;
        }

        char childChar = child.word;
        if(word.equals("网络") && index == 2){
            System.out.println(bug_index++);
        }
        // node char 大于 child char 右结点处理
        if (nodeChar > childChar)
        {
            if (current.right == null)
            {
                current.right = new TreeNode(nodeChar, index == word.length());
            }
            if (current.right.word != nodeChar)
            {
                index = index - 1;
            }else if(index == word.length()){
                current.right.isEnd = true;
                return;
            }

            nodeInsertToTree(current.right, word, index);
        }
        // // node char 小于 child char 左结点处理
        else if (nodeChar < childChar)
        {
            if (current.left == null)
            {
                current.left = new TreeNode(nodeChar, index == word.length());
            }
            if (current.left.word != nodeChar)
            {
                index = index - 1;
            }else if(index == word.length()){
                current.left.isEnd = true;
                return;
            }

            nodeInsertToTree(current.left, word, index);
        }
        else
        {
            nodeInsertToTree(current.child, word, index);
        }
    }

    /**
     * 检查树中是否包含该词
     * 
     * @param word
     * @return
     */
    public boolean contains(String word)
    {
        return search(root, word, 0);
    }
    
    private boolean search(TreeNode current, String word, Integer index)
    {
        if (current == null)
        {
            return false;
        }

        char currentChar = current.word;
        char nodeChar = word.charAt(index);

        if (nodeChar == currentChar)
        {
            if (index == word.length() - 1)
            {
                return current.isEnd;
            }
            index++;
            nodeChar = word.charAt(index);
        }
        
        TreeNode child = current.child;
        if(child == null){
            return false;
        }
        char childChar = child.word;

        if (nodeChar == childChar)
        {
            return search(current.child, word, index);
        }
        else if (nodeChar > childChar)
        {
            return search(current.right, word, index);
        }
        else if (nodeChar < childChar)
        {
            return search(current.left, word, index);
        }

        return false;
    }
    

    public int getCount()
    {
        return count;
    }

    public static void main(String[] args) throws IOException
    {
//        TreeBuild tree = TreeBuild.create();
//        LineIterator lines = IOUtils.lineIterator(TreeBuild.class
//                .getResourceAsStream("wordlist.txt"), "gbk");
//        while (lines.hasNext())
//        {
//            String word = lines.nextLine();
//            tree.addWord(word);
//        }
//
//        System.out.println(tree.contains("阿波罗神"));
    }
}
